import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

//合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
public class Solution {

      public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
      }

      //方法一 优先级队列 堆排序
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            //小顶堆
            Queue<ListNode> pq1 = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

            //遍历所有链表第一个元素
            for(int i = 0; i < lists.size();i++){
                if(lists.get(i) != null){
                    pq1.add(lists.get(i));
                }
            }
            //加一个表头
            ListNode res = new ListNode(-1);
            ListNode head = res;
            //直到小顶堆为空
            while(!pq1.isEmpty()){
                //取出最小的元素
                ListNode temp = pq1.poll();
                //连接
                head.next = temp;
                head = head.next;
                //每次取出链表的后一个元素加入小顶堆
                if(temp.next != null)
                    pq1.add(temp.next);
            }
            //去掉表头
            return res.next;
        }
    }

